package com.leetcode.tree.traversal;

import com.leetcode.basic.TreeNode;

/**
 * @author Dennis Li
 * @date 2020/7/30 17:01
 */
public class PreBuildTree_105 {

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if(preorder.length == 0 || inorder.length == 0) return null;
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
    }

    public TreeNode buildTree(int[] p, int pl, int pr, int[] in, int il, int ir) {
        if (pl > pr) return null;
        int k;
        for (k = il; in[k] != p[pl]; k++) ;
        // 计算左子树的长度，注意是减去il
        int left = k - il;
        TreeNode node = new TreeNode(p[pl]);
        // pre要排除pl点 -- 作为根节点
        // in要排除k点 -- 作为根节点
        node.left = buildTree(p, pl + 1, pl + left, in, il, k - 1);
        node.right = buildTree(p, pl + left + 1, pr, in, k + 1, ir);
        return node;
    }


}
